package cn.hy.today;

import datastruct.UnionFind;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution_1631 {
    public int minimumEffortPath(int[][] heights) {
        List<Edge> edgeList = new ArrayList<>();
        int n = heights.length, m = heights[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int id = i * m + j;
                if (i > 0) {
                    // 从上一行移动过来 (起点 从当前位置要减去 m)
                    edgeList.add(new Edge(id - m, id, Math.abs(heights[i][j] - heights[i - 1][j])));
                }
                if (j > 0) {
                    // 从上一列移动过来（从当前位置-1)
                    edgeList.add(new Edge(id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])));
                }
            }
        }
        // 将所有边从小到大排序
        edgeList.sort(Comparator.comparingInt(e -> e.dist));

        int ans = -1;
        UnionFind uf = new UnionFind(n * m);
        for (Edge edge : edgeList) {
            int x = edge.x, y = edge.y, d = edge.dist;
            uf.union(x, y);
            if (uf.connected(0, m * n - 1)) {
                ans = d;
                break;
            }
        }
        return ans;
    }


    class Edge {
        int x; // 边的起点
        int y; // 边的终点
        int dist;// 权重

        public Edge(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
}